/*-------------------------------------------------------------------------
 *
 * ilist.c
 *	  支持集成/内联双向和单向链表
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/lib/ilist.c
 *
 * NOTES
 *	  本文件仅包含太大而无法考虑内联的函数。有关大多数功能，请参见 ilist.h。
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "lib/ilist.h"

/*
 * 从列表中删除 'node'。
 *
 * 不允许删除不在列表 'head' 中的 'node'。
 *
 * 注意：这是 O(n)；考虑使用 slist_delete_current() 代替。
 */
void slist_delete(slist_head *fc_head, slist_node *fc_node)
{
	slist_node *fc_last = &fc_head->head;
	slist_node *fc_cur;
	bool		fc_found PG_USED_FOR_ASSERTS_ONLY = false;

	while ((fc_cur = fc_last->next) != NULL)
	{
		if (fc_cur == fc_node)
		{
			fc_last->next = fc_cur->next;
#ifdef USE_ASSERT_CHECKING
			fc_found = true;
#endif
			break;
		}
		fc_last = fc_cur;
	}
	Assert(fc_found);

	slist_check(fc_head);
}

#ifdef ILIST_DEBUG
/*
 * 验证双向链表的完整性
 */
void dlist_check(dlist_head *fc_head)
{
	dlist_node *fc_cur;

	if (fc_head == NULL)
		elog(ERROR, "doubly linked list head address is NULL");

	if (fc_head->head.next == NULL && fc_head->head.prev == NULL)
		return;					/* 好，初始化为零 */

	/* 向前迭代 */
	for (fc_cur = fc_head->head.next; fc_cur != &fc_head->head; fc_cur = fc_cur->next)
	{
		if (fc_cur == NULL ||
			fc_cur->next == NULL ||
			fc_cur->prev == NULL ||
			fc_cur->prev->next != fc_cur ||
			fc_cur->next->prev != fc_cur)
			elog(ERROR, "doubly linked list is corrupted");
	}

	/* 向后迭代 */
	for (fc_cur = fc_head->head.prev; fc_cur != &fc_head->head; fc_cur = fc_cur->prev)
	{
		if (fc_cur == NULL ||
			fc_cur->next == NULL ||
			fc_cur->prev == NULL ||
			fc_cur->prev->next != fc_cur ||
			fc_cur->next->prev != fc_cur)
			elog(ERROR, "doubly linked list is corrupted");
	}
}

/*
 * 验证单向链表的完整性
 */
void slist_check(slist_head *fc_head)
{
	slist_node *fc_cur;

	if (fc_head == NULL)
		elog(ERROR, "singly linked list head address is NULL");

	/*
	 * 在单向链表中，我们能测试的东西不多，除了它
	 * 实际上在某个时候结束，即没有引入循环或类似的情况
	 */
	for (fc_cur = fc_head->head.next; fc_cur != NULL; fc_cur = fc_cur->next)
		;
}

#endif							/* ILIST_DEBUG */
